/**
 * KMP  leetcode相关题 28 、796 、459 、686
 * KMP算法 : 解决字符串的匹配问题,
 * 前缀表:包含首字母,不包含尾字母的所有子串 
 * 后缀表:包含尾字母,不包含首字母的所有子串
 * 
 * 例如: 文本串:'aabaabaaf', 模式串:'aabaaf'
 * 
 * 以模式串为例
 *  
 * 前缀表:a、aa、aab、aaba、aabaa；
 * 后缀表：f、af、aaf、baaf、abaaf； 
 * 
 * 最长相等前后缀 [0,1,0,1,2,0]
 * a         0
 * aa        1
 * aab       0
 * aaba      1
 * aabaa     2
 * aabaaf    0 
 */
class KMP {
    constructor() { }
    getNext (str) {
        const len = str.length, next = [0]
        let j = 0;
        for (let i = 1; i < len; i++) {
            while (j > 0 && str[i] != str[j]) j = next[j - 1]
            if (str[i] == str[j]) j++
            next[i] = j
        }
        console.log(next)
        return next
    }
    // 找出字符串中第一个匹配项的下标,不存在则返回 -1
    match (s1, s2) {
        const len1 = s1.length, len2 = s2.length, next = this.getNext(s2)
        let j = 0
        for (let i = 0; i < len1; i++) {
            while (j > 0 && s1[i] != s2[j]) j = next[j - 1]
            if (s1[i] == s2[j]) j++
            if (j == len2) return i - j + 1
        }
        return -1
    }
}

let kmp = new KMP()
// kmp.getNext('aacecaaa') // [0, 1, 0, 0, 0, 1, 2, 2]
// kmp.getNext('aacecaaa#aaacecaa') // [0, 1, 2, 0, 0, 0, 1, 2, 3]
kmp.getNext('abcd#dcba')


// kmp.match("mississippi", "issip")
